package uestc.lj.basic.recall;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 1. 打印一个字符串的全排列
 * 2. 打印一个字符串的全排列且不要求重复
 *
 * @Author:Crazlee
 * @Date:2021/11/25
 */
public class Code04_PrintAllPermutations {

	public static ArrayList<String> Permutations(String str) {
		ArrayList<String> res = new ArrayList<>();
		if (str == null || str.length() == 0) {
			return res;
		}
		char[] charArray = str.toCharArray();
		process1(charArray, 0, res);
		return res;
	}

	private static void process1(char[] str, int i, ArrayList<String> res) {
		if (i == str.length) {
			res.add(Arrays.toString(str));
		}
		for (int j = i; j < str.length; j++) {
			swap(str, i, j);
			process1(str, i + 1, res);
			swap(str, i, j);
		}
	}

	private static void swap(char[] str, int i, int j) {
		char tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}

	public static ArrayList<String> PermutationsWithNoReply(String str) {
		ArrayList<String> res = new ArrayList<>();
		if (str == null || str.length() == 0) {
			return res;
		}
		char[] chars = str.toCharArray();
		process2(chars, 0, res);
		return res;
	}

	private static void process2(char[] chars, int i, ArrayList<String> res) {
		if (i == chars.length) {
			res.add(Arrays.toString(chars));
		}
		boolean[] visited = new boolean[26];
		for (int j = i; j < chars.length; j++) {
			if (!visited[chars[j] - 'a']) {
				visited[chars[j] - 'a'] = true;
				swap(chars, i, j);
				process2(chars, i + 1, res);
				swap(chars, i, j);
			}
		}
	}
}
